/*
 * @FilePath: \undefinedc:\Users\sxjct\.leetcode\120.三角形最小路径和.cpp
 * @Brief: 
 * @Version: 1.0
 * @Date: 2021-03-19 20:59:38
 * @Author: tianyiyi
 * @Copyright: Copyright@tianyiyi
 * @LastEditors: Mr.Tian
 * @LastEditTime: 2021-03-19 21:35:40
 */
/*
 * @lc app=leetcode.cn id=120 lang=cpp
 *
 * [120] 三角形最小路径和
 */

// @lc code=start
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int height = triangle.size();       // 三角形高度
        if(height == 0)
            return 0;
        vector<int> dp(triangle[height - 1].size() + 1,0);
        for(int i = height - 1 ; i >= 0 ;i--)
        {
            for(int j = 0;j < triangle[i].size();j++)
            {
                dp[j] = min(dp[j],dp[j+1]) + triangle[i][j];
            }
        }
        return dp[0];
    }
};
// @lc code=end

